Вперед: Приближённое нахождение точки экстремума Наверх: Приближённое нахождение корней уравнений Назад: Метод Ньютона (метод касательных)  

Метод хорд (метод линейной интерполяции)

Метод простых итераций во всех рассмотреннных вариантах использует для построения очередного приближения $ x_{i+1}$ только информацию о функции в одной лишь точке $ x_i$; при этом никак не используются предыдущие значения $ x_{i-1}, x_{i-2},\dots\;.$ Однако эту предыдущую информацию также можно использовать при нахождении $ x_{i+1}$. В качестве примера такого метода мы приведём метод, основанный на нахождении $ x_{i+1}$ по двум предыдущим приближениям $ x_i$ и $ x_{i-1}$ с помощью линейной интерполяции, называемый методом хорд.

Идея метода состоит в том, что по двум точкам $ M_{i-1}(x_{i-1};f(x_{i-1}))$ и $ M_i(x_i;f(x_i))$ построить прямую $ M_{i-1}M_i$ (то есть хорду, соединяющую две точки графика $ y=f(x)$) и взять в качестве следующего приближения $ x_{i+1}$ абсциссу точки пересечения этой прямой с осью $ Ox$. Иными словами, приближённо заменить на этом шаге функцию $ f(x)$ её линейной интерполяцией, найденной по двум значениям $ x$: $ x_{i-1}$ и $ x_i$. (Линейной интерполяцией функции $ f(x)$ назовём такую линейную функцию $ \ell(x)$, значения которой совпадают со значениями $ f(x)$ в двух фиксированных точках, в данном случае -- в точках $ x_{i-1}$ и $ x_i$.)

В зависимости от того, лежат ли точки $ x_{i-1}$ и $ x_i$ по разные стороны от корня $ x^*$ или же по одну и ту же сторону, получаем такие чертежи:

Рис.9.14.Построение последовательного приближения по методу хорд: два случая


Итак, очередное последовательное приближение будет зависеть от двух предыдущих: $ x_{i+1}={\varphi}(x_{i-1};x_i)$. Найдём выражение для функции $ {\varphi}$.

Интерполяционную линейную функцию $ \ell(x)$ будем искать как функцию с угловым коэффициентом, равным разностному отношению

$\displaystyle k_i=\dfrac{f(x_i)-f(x_{i-1})}{x_i-x_{i-1}},$

построенному для отрезка между $ x_{i-1}$ и $ x_i$, график которой проходит через точку $ M_i$:

$\displaystyle \ell(x)=f(x_i)+\dfrac{f(x_i)-f(x_{i-1})}{x_i-x_{i-1}}(x-x_i).$

Решая уравнение $ \ell(x)=0$, находим

$\displaystyle x_{i+1}=\dfrac{x_{i-1}f(x_i)-x_if(x_{i-1})}{f(x_i)-f(x_{i-1})}= x_i-\dfrac{f(x_i)}{\dfrac{f(x_i)-f(x_{i-1})}{x_i-x_{i-1}}},$

то есть

$\displaystyle x_{i+1}=x_i-\dfrac{f(x_i)}{k_i}.$ (9.3)

Заметим, что величина $ k_i$ может рассматриваться как разностное приближение для производной $ f'(x)$ в точке $ x_i$. Тем самым полученная формула (9.3) -- это разностный аналог итерационной формулы метода Ньютона.

Вычисление по формуле (9.3) гораздо предпочтительнее вычисления по другой полученной нами формуле

$\displaystyle x_{i+1}=\dfrac{x_{i-1}f(x_i)-x_if(x_{i-1})}{f(x_i)-f(x_{i-1})},$

хотя эти две формулы математически тождественны, поскольку при использовании формулы (9.3) в случае вычислений с округлениями (например, на компьютере) достигается меньшая потеря значащих цифр.

Имеются две разновидности применения формулы (9.3).

Первая разновидность: вычисления ведутся непосредственно по формуле (9.3) при $ i=1,2,3,\dots$, начиная с двух приближений $ x_0$ и $ x_1$, взятых, по возможности, поближе к корню $ x^*$. При этом не предполагается, что $ x^*$ лежит между $ x_0$ и $ x_1$ (и что значения функции $ f$ в точках $ x_0$ и $ x_1$ имеют разные знаки). При этом не гарантируется, что корень попадёт на отрезок между $ x_{i-1}$ и $ x_i$ на каком-либо следующем шаге (хотя это и не исключено). В таком случае затруднительно дать оценку погрешности, с которой $ x_{i+1}$ приближает истинное значение корня $ x^*$, и поэтому довольствуются таким эмпирическим правилом: вычисления прекращают, когда будет выполнено неравенство $ \vert x_{i+1}-x_i\vert<{\varepsilon}$, где $ {\varepsilon}$ -- желаемая точность нахождения корня. При этом полагают приближённое значение корня равным $ \wt x=x_{i+1}$.

        Пример 9.8   Решим уравнение $ x^3+2x^2+3x+5=0$ методом хорд. Зададимся точностью $ {\varepsilon}=0.000001$ и возьмём в качестве начальных приближений $ x_0$ и $ x_1$ концы отрезка, на котором отделён корень: $ x_0=-2,x_1=-1$. Итерационная формула метода хорд при $ f(x)=x^3+2x^2+3x+5$ имеет вид

$\displaystyle x_{i+1}=x_i-\dfrac{f(x_i)}{\dfrac{f(x_i)-f(x_{i-1})}{x_i-x_{i-1}}... ...dfrac{(x_i^3+2x_i^2+3x_i+5)-(x_{i-1}^3+2x_{i-1}^2+3x_{i-1}+5)} {x_i-x_{i-1}}}.$    

По этой формуле последовательно получаем:

\begin{multline*} x_2=-1.75;x_3=-1.905660; x_4=-1.840182; x_5=-1.843603;\\ x_6=-1.843735; x_7=-1.843734; x_8=-1.843734. \end{multline*}

Седьмое приближение уже дало нам значение корня с нужной точностью; восьмая итерация понадобилась для того, чтобы убедиться: с заданной точностью значение перестало изменяться. Получаем, что $ \wt x=-1.843734$.     

        Упражнение 9.3   Проведите вычисления тем же методом, переставив местами начальные приближения $ x_0$ и $ x_1$, то есть взяв $ x_0=-1, x_1=-2$. Убедитесь, что получаются другие значения для $ x_3,x_4,\dots$ и что с точностью $ {\varepsilon}$ уже $ x_6$ равняется искомому корню.     

        Пример 9.9   Проверим, что метод работает и в том случае, если $ x_0$ и $ x_1$ взяты по одну и ту же сторону от корня (то есть если корень не отделён на отрезке между начальными приближениями). Возьмём всё для того же уравнения $ x_0=-1.5$ и $ x_1=-1$. Тогда

\begin{multline*} x_2=-2.090909; x_3=-1.700772; x_4=-1.823138; x_5=-1.845616;\\ x_6=-1.843711; x_7=-1.843734; x_8=-1.843734. \end{multline*}

Мы получили то же значение $ \wt x$, причём за то же число итераций. Может показаться, что было бы выгоднее расположить начальные приближения иначе, так чтобы $ x_1$ было ближе к корню, чем $ x_0$. Однако при этом получаем фактически ту же скорость сходимости, можно заметить лишь небольшое ускорение:

\begin{multline*} x_2=-2.090909; x_3=-1.791404; x_4=-1.836390; x_5=-1.843972;\\ x_6=-1.843733; x_7=-1.843734; x_8=-1.843734. \end{multline*}

Понадобились всё те же семь вычислений.     

Вторая разновидность применения формулы (9.3) называется методом ложного положения. Предположим, что корень $ x^*$ отделён на отрезке между $ x_0$ и $ x_1$, то есть значения $ f(x_0)$ и $ f(x_1)$ -- разных знаков. После вычисления $ x_{i+1}$ по формуле (9.3) на очередном, $ i$-м, этапе из двух отрезков: между $ x_{i-1}$ и $ x_{i+1}$ и между $ x_i$ и $ x_{i+1}$ -- выбирают тот, в концах которого функция $ f$ принимает значения разных знаков. Если это отрезок между $ x_{i-1}$ и $ x_{i+1}$, то производят перенумерацию предыдущих приближений, то есть полагают $ x_i$ равным $ x_{i-1}$, а затем повторяют вычисления по формуле (9.3). Этим достигается, что при любом $ i$ корень $ x^*$ располагается на отрезке между $ x_i$ и $ x_{i+1}$, так что при выполнении условия $ \vert x_{i+1}-x_i\vert<2{\varepsilon}$, где $ {\varepsilon}$ -- желаемая точность нахождения корня, вычисления можно прекратить и взять приближённое значение корня равным $ \wt x=x_{i+1}$. При этом гарантируется, что будет выполнено неравенство $ \vert\wt x-x^*\vert<{\varepsilon}$, то есть корень будет определён с нужной точностью.

Такое усложнение алгоритма не даёт, на самом деле, сколько-нибудь заметного преимущества. Проиллюстрируем это на примере.

        Пример 9.10   В ситуации примера 9.8 применим метод ложного положения. Тогда последовательные приближения будут такими:

\begin{multline*} x_2=-1.75; x_3=-1.835052; x_4=-1.842950; x_5=-1.843664;\\ x_6=-1.843728; x_7=-1.843734; x_8=-1.843734. \end{multline*}

Как мы видим, отличаются от вычислений в примере 9.8 только приближения $ x_3,x_4,x_5,x_6$. (Заметим, что если бы в примере 9.8 мы взяли $ x_0=-1, x_1=-2$, см. упражнение 9.3, то вдобавок совпали бы значения $ x_3$.)     


Вперед: Приближённое нахождение точки экстремума Наверх: Приближённое нахождение корней уравнений Назад: Метод Ньютона (метод касательных)